package exam;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author DengYuan2
 * @create 2021-03-26 19:59
 */
public class Test1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入钱数");
        int money = Integer.parseInt(scanner.nextLine());
        System.out.println("输入物品价格");
        String stuff = scanner.nextLine();
        String[] s = stuff.split(" ");
        int[] price=new int[s.length];
        for (int i = 0; i < s.length; i++) {
            price[i]=Integer.parseInt(s[i]);
        }
        Test1 test1 = new Test1();
        int res = test1.getResult(money, price);
        System.out.println(res);

    }

    public int getResult(int money,int[] stuff){
        int[] value=new int[money+1];
        boolean isBought=false;
        for (int i = 0; i < stuff.length; i++) {
            isBought=false;
            for (int j = 1; j <= money; j++) {
                //如果商品价格大于钱数
                if (stuff[i]>j ){
                    value[j]=value[j-1];
                }else {
                    if (!isBought){
                        isBought=true;
                        int max1=value[j-1];
                        int max2=stuff[i]+value[j-stuff[i]];
                        int max=max1>max2?max1:max2;
                        value[j]=max;
                    }else {
                        value[j]=value[j-1];
                    }
                }
            }
        }
        System.out.println("谈团第二次提交内容-----");
        System.out.println(Arrays.toString(value));
        int res=value[money];
        return res;
    }
}
